package algorithm.dynamic;

/**
 * Related Topics ：Greedy  Array
 *
 * leetcode : https://leetcode.com/problems/jump-game-ii/
 * Difficulty : Hard
 *
 * JumpGame的进阶版。
 * 给一个非负数组，数组中的元素代表以该点为起点可以跳动的格子数。
 * 目标是以最小的跳跃次数，达到最后一个格子。求这个次数
 *
 * Example:
 * Input:[2,3,1,1,4]
 * output: 2
 * 因为最短可以跳2次到达最后
 *
 * 解题思路：
 * BFS  （参考:https://leetcode.com/problems/jump-game-ii/discuss/18028/O(n)-BFS-solution）
 * Greedy
 *
 * @Author Antony
 * @Since 2018/11/6 17:47
 */
public class JumpGameII {

    public static void main(String[] args) {
        int[] arr = new int[]{2,3,1,1,4};
        System.out.println(jump(arr));
    }


    /**
     * leetcode : 6ms - beats 86.65%
     * 思路：BFS
     *
     * 1）第一个算第一层，然后遍历，算出能达到下一层的最大索引值。
     * 2）每跳一次到下一层，level+1
     * 3）如果计算出的nextMax大于数组最后一个索引（len-1），那说明已经可以到达末尾了。直接返回level
     * @param nums
     * @return
     */
    public static int jump(int[] nums){
        if(nums.length < 2){
            return 0;
        }
        int len = nums.length;
        int level=0;    // 当前层数
        int i=0;        // 当前位置的索引
        int currentMax=0, nextMax=0;    // 当前层数的最大索引值，以及下一层的最大索引值
        while(currentMax-i+1 > 0){
            level++;
            for(;i<=currentMax;i++){
                nextMax = Math.max(nextMax, nums[i]+i);
                if(nextMax >= len-1) return level;
            }
            currentMax = nextMax;
        }

        return 0;
    }
}
